%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End:

\documentclass[a4paper, 11pt]{article}
\usepackage{amsmath}

\begin{document}

\title{DatorCurling}
\author{Jens Lindblad\\and\\Henrik Hansson}
\date{\today}
\maketitle
\abstract{A curling game has been created as part of a course in computer graphics. This report contains a description of the project and some thoughts on the result.}

\section{Introduction}
This report describes the outline and implementation of a computer based curling game. The goal of the project has been to create a simplified curling game containing the most important elements of curling.

The project started out as a pool game and initially had four members. The poor suitability for the game of pool as a computer game, and an overly complex design, caused general disinterest and concensus was reched to scrap the idea and start over. Curling was chosen instead. Once again interest faded and two members of the group deserted. Left was Henrik Hansson and Jens Lindblad.

\subsection{The game of curling}
It is not known where the game of curling first came about, but paintings of similar activity exist from the 16th century \cite{curling-history}. Modern curling is played on a 45.720m by 5.000m ice surface called the \emph{rink} \cite{curling-rules}. Two teams compete by sliding granite stones from one end of the rink towards the centre of a set of concentric circles on the other end called the \emph{house}. Each team consists of four player taking turns playing a total of eight stones. When all stones have been played points are awarded to the team with the most stones closest to the centre of the house.

\subsection{Specification}
We will do a 3d curling game where two players can play against each other. The game will 
consist of a menu where you can select game type and when the game is started a 3d-arena 
with audience in 2d and several lanes will appear. The players can then play curling using 3d stones and rules according to \textsc{wcf} (World Curling Federation).

\subsubsection{Will do}
\begin{itemize}
\item{A textures 3d-arena and lanes.}
\item{A start menu where game type can be selected.}
\item{Stone collision detection with walls and other stones.}
\item{Several cameras following the game.}
\item{Scoreboard.}
\item{Light sources.}
\item{Sound effects.}
\item{Classic powermeter controlling power, direction, and curl.}
\item{Basic curling ruleset (arcade style).}
\end{itemize}

\subsubsection{Might do}
\begin{itemize}
\item{Simple \textsc{ai} for \textsc{cpu} player.}
\item{Simple animations of audience and players.}
\item{Team entrance and exit animations.}
\item{Detailed arena incluing entrances for players and audience.}
\item{Audience reactions (sound, animations).}
\item{Selectable teams with differing strengths.}
\item{Instant replays.}
\item{Aiming system using player and powermeter.}
\item{Complete ruleset.}
\end{itemize}

\section{Implementation}
This section describes the implementation of the game. First the structure of the program is presented, followed by an overview of graphics, sound, and physics.

\subsection{Tools}
The game has been developed cross-platform in the form of a Mac version and a Windows version. To facilitate this a library called \textsc{glfw} \cite{glfw} has been used.
 
\subsubsection{Mac OS X development}
Development on Mac OS X has mainly been done in XCode with the standard Subversion command-line client for repository access.

\subsubsection{Windows development}
Development on Microsoft Windows has mainly been done in Microsoft Visual Studio 2005.

\subsection{Assets}
The game contains images and sounds which copyrights are held by people outside the project group. All such copyrights are described in the file \verb!copyright.txt! inside the \verb!data! directory. Copyrights are also presented in game and/or in the readme file as necessary. Some sounds have been downloaded from \emph{The Freesound Project} \cite{freesound} and \emph{Soundsnap.com} - both excellent sources for free sound samples. All 3d objects are procedurally generated or hard coded.

\subsection{Program structure}
The program is separated into five parts: the platform, the core, the game logic, the user interface, and the renderer.

\subsubsection{The Platform}
The platform is simply the part of the program that is responsible for setting up the application and opening the main window. Since \textsc{glfw} is used for this the platform is mainly platform independent. It is however possible to customize this part of the application to accomodate for things that \textsc{glfw} cannot handle.

\subsubsection{The Core}
The core - as the name implies - is central to the program. It is responsible for setting up (and managing the lifetime of) the user interface, the renderer, and the game.

Central to the core is a state machine which controls what is currently going on. The core receives notifications from the user interface and game logic. These notifications work as events to the state machine. When an event is received in a state changes to the user interface and game logic are performed.

\subsubsection{The Game Logic}
The game logic is separated into three main classes: \verb!game_t!, \verb!rink_t!, and \verb!stone_t!. While \verb!game_t! implements both rules and user actions, the other classes are mainly used for the physics simulation.

The \verb!game_t! class contains the main game logic. Internally it consists of a state machine which keeps track of the current phase of play. State transitions are initiated both by the simulation and by user actions which are dispatched via the core.

The \verb!rink_t! class contains data describing the rink being played, and owns the associated curling stones. It is also responsible for the physics simulation and tells each stone to step one frame before it resolves any collisions.

The \verb!stone_t! class represents a single curling stone and contains the necessary physics code responsible for simulating the sliding motion of the stone. For convenience some extra information such as if it is a point stone or if the stone is in play is also stored. While this may look like a case of mixed responsibilities (why would a physical stone know if it is a point stone?) it fulfills the requirements well and keeps code bloat to a minimum.

\subsubsection{The User Interface}
A giant monolithic class called \verb!gui_t! is responsible for the entire user interface. While - for historical reasons - it is called \verb!gui_t! it is not only reponsible for the graphical aspects of the user interface. In fact, it only represents an abstract interface since the actual rendering of both graphics and sounds is handled by the renderer.

Most graphical elements observed by the user can be controlled via the user interface class. Each menu ingame can be shown or hidden simply by calling the appropriate function, such as \verb!show_start_menu()!.

The user interface class also controls a number of cameras which can be switched between by calling \verb!switch_camera(new_camera)! or \verb!animate_to_camera(new_camera, time)!. The former switches to the new camera instantaneous while the latter performs a linear interpolation from the previous camera to the new camera in the specified time frame.

The user interface class also holds information on what options are currently selected, which can then be read back when the user confirms the selection. Key strokes by the user are interpreted in context based on what user interface features have been enabled. The user action is then sent as a notification to other parts of the program that have registered as listeners.

\subsubsection{The Renderer}
The presentation of graphics and sounds to the user is handled by the renderer. To keep it simple it has been divided into only two classes: \verb!renderer_t! and \verb!stone_renderer_t!.

The main class \verb!renderer_t! does most of the rendering of both the user interface and arena. It also controls music and arena ambiance sounds.

The stone renderer \verb!stone_renderer_t! does the rendering of a single stone. This has mainly to do with keeping track of the sliding sound made by the stone which must be controlled individually.

\subsection{Physics}
Physics are a central concept in the game of curling. While this game focuses on being fun, the curling stones should still behave in a somewhat realistic manner. Otherwise it wouldn't really be curling but some other game on ice. Thus they should curl when played and respond to interactions by other stones.

The physics formulas used in this chapter should be found in most textbooks covering \emph{classical mechanics} such as \emph{The Physics Handbook: Fundamentals and Key Equations} \cite{physics}.

The physics engine works using a delta time $\Delta t$ for each frame of animation. This time depends on how long the last frame took to render. This method has its share of drawbacks, mainly that by not having a constant $\Delta t$ the physics becomes nondeterministic, but it has been deemed good enough for this game.

\subsubsection{Sliding}
Each stone has a position $p$, a velocity $\vec{v}$, and an angular velocity $\omega$. At each iteration the next position of the stone needs to be calculated. This involves computing the total force $F$ acting on the stone in the current frame.

The frictional force is expressed as $F_f = \mu_{s} F_n$ where $\mu_{s}$ is the \emph{coefficitient of kinetic friction} between the granite and the ice surface, and $F_n$ is the normal force here expressed as $F_n = mg$ since the stone's normal is perpendicular to the ice surface.

The curl comes from a force $F_c$ perpendicular to the sliding direction of the stone, and is approximated as another frictional force with friction coefficient $\mu_{c}$. The coefficient is dependent on the angular velocity and the speed of the stone. Since
\begin{displaymath}F_c = ma \Leftrightarrow a = \frac{F_c}{m}\end{displaymath}
applying this force during $\Delta t$ time will result in a velocity change of
\begin{displaymath}\Delta v_c = \frac{F_c}{m} \Delta t .\end{displaymath}
If the kinetic energy is expressed as
\begin{displaymath}E_k = \frac{1}{2}mv_c^2\end{displaymath}
the energy added to the system is
\begin{displaymath}E_k = \frac{1}{2}m(\frac{F_c}{m} \Delta t)^2 = \frac{1}{2}\frac{{F_c}^2}{m}{\Delta t}^2 .\end{displaymath}
This energy must come from the rotational energy
\begin{displaymath}E_r = \frac{1}{2}I\omega^2\end{displaymath}
where $I$ is the moment of inertia. For a solid disk (a good approximation of a curling stone)
\begin{displaymath}I = \frac{1}{2}mr^2 \Rightarrow E_r = \frac{1}{4}mr^2\omega^2.\end{displaymath}
The resulting rotational energy becomes $E_r' = E_r - E_k$, and the resulting angular velocity can be expressed as
\begin{displaymath}\omega = \frac{2}{r}\sqrt{\frac{E_r - E_k}{m}}.\end{displaymath}

The total force can thus be expressed as $F = F_f + F_c$ and since $F = ma \Leftrightarrow a = \frac{F}{m}$ the new velocity of the stone becomes $\vec{v}' = \vec{v} + \frac{F}{m} \Delta t$. The new position of the stone can be expressed similarly as $p' = p + \vec{v}' \Delta t$.

The question then is what values of $\mu_s$ and $\mu_c$ to choose. One web page \cite{curlingfriction} mentions $\mu_s = 0.0168$. This value originally comes from an article which has proved difficult to obtain. However, using this coefficient in the simulation has worked well and gives a good indication that the simulation behaves properly. The case for $\mu_c$ is a litte more complicated. Right now it is tweaked to work and is chosen so that a high velocity results in less bite for the curling motion.

The above describes the basics of the physics engine. The actual implementation may differ slightly, perhaps to tweak the physics to better fit the game without ending up neck deep in difficult physics concepts. It should be noted however, that having an elegant mathematical description of the movement of the curling stones is not just about cosmetics, it is also of great importance in making a good \textsc{ai}. For more information see the \textsc{ai} chapter.

\subsubsection{Collision Detection and Handling}
As each stone is represented as a point $p$ and a radius $r$, stones $A$ and $B$ are said to collide if
\begin{displaymath}\lvert p_A - p_B \rvert - (r_A+r_B) \leq 0.\end{displaymath}
Handling a collision between two stones can be tricky enough, but handling a collision between an arbitrary number of stones requires solving a system of equations. Instead of embarking on such a difficult journey the solution chosen has been to simply handle collisions between any two stones and implicitly solving the system by repeating this process many times per second as the simulation continues.

At each iteration stone $A$ is checked against all other stones. If there is a collision with stone $B$, it has to be resolved. The stones are first moved apart so they barely touch. This is done by computing the position delta $\Delta p = p_A - p_B$. Then
\begin{displaymath}p_A' = p_A + \lvert \hat{\Delta p} \rvert \frac{1}{2} (r_A + r_B - \lvert \Delta p \rvert)\end{displaymath}
and $p_B'$ is computed similarly but instead by subtraction.

The second step is to compute the new velocities. This is simplified by considering the stones to have the same mass. Since curling stones are very solid, the collisions are also considered non-elastic. That means the stones can only exchange kinetic energy in a collision, and that no energy is lost. With the same mass this means only the velocities of the stones are of interest. Another important thing is that energy is only exchanged over the collision axis $\hat{\Delta p}$. These components are computed as $e_A = \hat{\Delta p} \cdot \vec{v_A}$ and $e_B = \hat{\Delta p} \cdot \vec{v_B}$, that is as the projection of $\vec{v_A}$ onto the collision axis which is a unity vector. The new velocities are then
\begin{displaymath}\vec{v_A}' = \vec{v_A} + \hat{\Delta p} (\lvert e_A \rvert + \lvert e_B \rvert)\end{displaymath}
and
\begin{displaymath}\vec{v_B}' = \vec{v_B} - \hat{\Delta p} (\lvert e_A \rvert + \lvert e_B \rvert).\end{displaymath}

This collision handling model cuts a few corners and probably has a few problems, but in practice it works well and no obvious errors have occurred during testing.

\subsection{Graphics}
Graphics have been implemented using \emph{OpenGL}. It is cross-platform and since most graphics have been done programmatically it has been deemed unnecessary to use more complicated libraries.

The user interface has been implemented using simple techniques such as rectangles with different opacity. Text rendering is done both using premade textures and with texture fonts using \emph{glFont 2} \cite{glfont}.

Since none of the project participants are great artists most of the ingame models have been created programmatically. Different sections have been created which can be combined by translation and rotation to form the arena. The curling stones are procedurally generated and rendererd two times, one time mirrored to create a realistic reflection on the ice surface. To give the arena a soft touch simple shadows are rendered at model intersections.

The rendering is done using OpenGL's fixed pipeline, so data is uploaded using \verb!glVertex!, \verb!glNormal!, and \verb!glTexCoord! at each frame, using \verb!glRotate! and \verb!glTranslate! to do transformations. A better method would be to use vertex arrays or vertex buffer objects to keep function calls to a minimum or to upload data only one time. The chosen method enabled quick prototyping however.

\subsection{Sound}
Since sounds adds another dimension to a game some energy has been devoted to this area. Standard for sports games is a title track which has been implemented. Arena ambiance has been implemented using a simple looping sample. It isn't very realistic, but obtaining samples of real curling events has been difficult. Sound has also been added for stones sliding and collisions.

The sound system used is \textsc{fmod} \cite{fmod} which is free for non-commercial uses. It was chosen because it is available for both Windows and Mac. It is also very easy to set up and get going with, and comes with handy functions for loading and streaming samples.

\subsection{Artificial Intelligence}
While no \textsc{ai} has been implemented, some thought has been devoted to the issue. The following is short discussion on the subject.

The game of curling is played as a series of moves. While each move may be complex to execute, they can each be described as a discrete operation with a well defined result. As such it is possible to reason about a game of curling using a tree of possible moves. Thus any standard method of finding the optimal move, such as alpha-beta pruning can be applied.

The problem then becomes one of finding valid moves to populate the tree with. As the number of possible moves are infinite the most general method is certainly to create a set of completely random moves. This does seem inefficient though, since most of the random moves would play a stone into a wall, rendering it useless, or putting stones in terrible positions.

Looking at how a game of curling is really played does help. Each move normally has a specific goal. It can be to put up a guard stone prohibiting the opposition from playing a stone into the home, taking out an opponent stone, or positioning a stone for points. By identifying these roles, it is possible to create a similar set of moves for each state-node in the move-tree. For point stones and guard stones, a number of evenly distributed random moves within a confined area can be generated. When taking out opponent stones a set of moves can be generated for each opponent stone, attacking it from different angles.

The above method requires that the physics behave in a deterministic way, and that each move can be ``solved'' easily, that is that it is easy to find the correct parameters for making the shot given a final position. Thus it is necessary to keep the physics elegant so that the corresponding equations can be solved mathematically.
 
\section{Conclusions}
%What have we done? What could we have done better? Lessons learned.
The finished project fulfills many but not all requirements. In many cases this can be traced back to the project management. When half the project's members quit a lot of work had been made on the foundation of the game, but a lot of work still had to be done primarily with the graphics and user interface. This meant extra work had to be put in by the remaining members in order to get the game into a polished state.

As the requirements specified, an arena has been implemented. This was necessary to get the ambiance right in the game. One can argue whether to use a full-scale arena or a practice-hall, but the arena presented better opportunities for open development. While an arena has been created though, it is a very bare-bones version. The audience is just rows of textured quads in pretty colors. And the detail level of the arena should have been much higher.

Likewise details in user interface are minimal and many planned features had to be cut. Especially the information presentation during an actual game is minimal. It is possible to see the score but there are few hints as to what is currently going on.

The ingame sounds should also have been more detailed. Implemented is a simple loop for the audience but no reactions to the actual game played are presented. The actual game sounds are also the bare minimum tolerable.

A big problem was how to do the actual graphics given that no person in the project group had much of a talent. Instead of doing fancy models and effects focus had to be put on programmatical generation of objects. Simple techniques such as manual shadows added some feeling to the environment.

Another interesting problem was how to get the curling physics to work in a believable way. After creating a simple physics system which was only loosely based in real physics (while still giving good results) more work was put in to use actual formulas. While it may not bring a lot of benefits in the game's current state, further development could benefit from it by being able to do real-life experiments and using obtained data in the simulation.

The intent to keep feature and complexity-bloat at a minimum by using only a few files and classes has worked remarkably well. While it is probably not a good idea to keep things this simple for an even larger project, it has presented minimal problems during the development of this game. Sometimes not strictly adhering to \emph{good} \textsc{oo} techniques has its benefits.

To summarise, given the constraints applied to the project, the resulting product is something both remaining developers do feel good about. The objective was to implement a curling game and while it might lack in most areas, and while a computer opponent would have been a nice addition, it is fully playable and certainly enjoyable.

% use \cite{notes} for inline citation
\begin{thebibliography}{1}
\bibitem{curlingfriction} Ableman, Genna {\em Coefficients of Friction for Ice} 2004: http://hypertextbook.com/facts/2004/GennaAbleman.shtml [last checked \date{July, 10, 2008}]
\bibitem{glfw} Berglund, Camilla {\em GLFW} 2007: http://glfw.sourceforge.net [last checked \date{July, 10, 2008}]
\bibitem{glfont} Fish, Brad {\em glFont 2.0} 2002: http://students.cs.byu.edu/\~{}bfish/ [last checked \date{July, 10, 2008}]
\bibitem{fmod} Firelight Technologies Pty, Ltd. {\em FMOD music \& sound effects system} 2008: http://fmod.org [last checked \date{July, 10, 2008}]
\bibitem{freesound} Music Technology Group, Universitat Pompeu Fabra {\em The Freesound Project} 2008: http://freesound.iua.upf.edu [last checked \date{July, 10, 2008}]
\bibitem{physics} Poole, Charles P. \& Poole, Charles P. Jr. {\em The Physics Handbook: Fundamentals and Key Equations} 2007: Wiley-VCH
\bibitem{curling-history} World Curling Federation {\em History of the World Curling Federation} 2008: http://www.worldcurling.org/content/blogsection/5/81 [last checked \date{July, 10, 2008}]
\bibitem{curling-rules} World Curling Federation {\em The Rules of Curling and Rules of Competition} 2007: http://www.worldcurling.org/images/PDF/wcf-newrulesofcurlingjune07.pdf [last checked \date{July, 10, 2008}]
\end{thebibliography}

%\appendix

%\section{User's Manual}
%Short game manual. Installation and usage.

\end{document} 
